home *** CD-ROM | disk | FTP | other *** search
/ Apple WWDC 1996 / WWDC96_1996 (CD).toast / Technology Materials / MacApp Release 10 / MacApp Release 10 - HD Ready / Libraries / ODMemMgr / Sources / BestFitH.cpp next >
Encoding:
C/C++ Source or Header  |  1996-04-03  |  38.8 KB  |  1,353 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        BestFitH.cpp
  3.  
  4.     Contains:    BestFitHeap class implementation
  5.  
  6.     Owned by:    Michael Burbidge
  7.  
  8.     Copyright:    © 1993 - 1995-96 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.                   3/5/96    TWB        Comment out unused arguments to suppress warnings. 
  12.                  2/13/96    srf        Build variation for MacApp
  13.         
  14.         <14>      8/4/95    DM        Leak checking [1267956]
  15.         <13>      5/4/95    jpa        Support for finding largest free block
  16.                                     [1235657] and validating memory ranges
  17.                                     [1246077]. Better calculation of dflt huge
  18.                                     block size [1233941]
  19.         <12>     2/14/95    jpa        Fixed DoIsValidBlock to do proper size
  20.                                     checking (was giving spurious warnings.)
  21.                                     [1215473]
  22.         <11>    12/20/94    jpa        Disallow case where fHugeBlockSize >
  23.                                     sizeIncrement. [1199188]
  24.         <10>     12/5/94    jpa        Nuked errant pragma lib_export's. [1195676]
  25.          <9>    10/24/94    jpa        Don't call CheckTree all over the place
  26.                                     unless gValidate>0.
  27.          <8>     9/29/94    RA        1189812: Mods for 68K build.
  28.          <7>     9/14/94    jpa        Eliminated dependencies on rest of OpenDoc.
  29.                                     Added support for getting the heap of a
  30.                                     block by stuffing heap ptr in busy block
  31.                                     header. [1186692]
  32.          <6>     8/17/94    jpa        Implemented huge-block support [1179565],
  33.                                     segment disposal [1181509] and the
  34.                                     SOM-block flag [1181510].
  35.          <5>      8/8/94    jpa        Added fHugeBlockSize -- not used yet
  36.                                     [1179565]
  37.          <4>      8/2/94    jpa        Install block cushion hooks. Allocate
  38.                                     blocks on 4byte boundaries. Fixed bug when
  39.                                     getting block size (didn't work right with
  40.                                     hooks installed.)
  41.          <3>     6/18/94    MB        Add #pragma lib_export lines
  42.          <2>     6/10/94    MB        Make it build
  43.          <1>      6/9/94    MB        first checked in
  44.          <5>     5/27/94    MB        #1165129: CreateNewSegment doesn't check
  45.                                     for NULL after allocating new segment.
  46.          <4>     5/27/94    MB        #1162181: Fixed MMM integration bug
  47.          <2>      5/9/94    MB        #1162181: Changes necessary to install MMM.
  48.          <1>     4/29/94    MB        first checked in
  49.          
  50.     To Do:
  51.     In Progress:
  52.         
  53. */
  54.  
  55. #ifndef _PLATFMEM_
  56. #include "PlatfMem.h"
  57. #endif
  58.  
  59. #ifndef _MEMMGRPV_
  60. #include "MemMgrPv.h"
  61. #endif
  62.  
  63. #ifndef _BESTFITH_
  64. #include "BestFitH.h"
  65. #endif
  66.  
  67. #if MM_DEBUG
  68. #ifndef _MEMHOOKS_
  69. #include "MemHooks.h"
  70. #endif
  71. #endif
  72.  
  73. #ifndef __MEMORY__
  74. #include <Memory.h>
  75. #endif
  76.  
  77. #ifndef __LIMITS__
  78. #include <limits.h>
  79. #endif
  80.  
  81. #ifndef __STRING__
  82. #include <string.h>
  83. #endif
  84.  
  85. #ifndef __STDIO__
  86. #include <stdio.h>
  87. #endif
  88.  
  89.  
  90. #define BLOCKS_ON_4BYTE 1        // Allocate blocks on 4-byte boundaries.
  91.  
  92.  
  93. #if MM_DEBUG
  94. //----------------------------------------------------------------------------------------
  95. // IsValidBlock
  96. //----------------------------------------------------------------------------------------
  97. #pragma segment HeapSeg
  98.  
  99. static const PrivBestFitBlock *ValidBlock(const void* ptr)
  100. {
  101.     if( ptr==kMMNULL )
  102.         return kMMNULL;
  103. #if BLOCKS_ON_4BYTE
  104.     if( (long)ptr & 0x00000003 )
  105.         return kMMNULL;                    // Not on a 4-byte boundary
  106. #endif
  107.         
  108.     const PrivBestFitBlock *blk 
  109.         = (const PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  110.  
  111.     ODBlockSize blkSize = blk->GetSize();
  112.     if( (blkSize >= PrivBestFitBlock::kMinBlockSize || blkSize <= BestFitBlock_kMaxBlockSize)
  113.             && blk->GetBusy()
  114.             && blk->GetMagicNumber() == (unsigned int)PrivBestFitBlock::kMagicNumber )
  115.         return blk;
  116.     else
  117.         return kMMNULL;
  118. }
  119. #endif
  120.  
  121. //========================================================================================
  122. // PrivBestFitBlock
  123. //========================================================================================
  124.  
  125. //----------------------------------------------------------------------------------------
  126. // PrivBestFitBlock::operator >
  127. //----------------------------------------------------------------------------------------
  128. #pragma segment HeapSeg
  129.  
  130. Boolean PrivBestFitBlock::operator>(const PrivBestFitBlock& blk) const
  131. {
  132.     if (GetSize() == blk.GetSize())
  133.         return this > &blk;
  134.     else
  135.         return GetSize() > blk.GetSize();
  136. }
  137.  
  138. //----------------------------------------------------------------------------------------
  139. // PrivBestFitBlock::operator <
  140. //----------------------------------------------------------------------------------------
  141. #pragma segment HeapSeg
  142.  
  143. Boolean PrivBestFitBlock::operator<(const PrivBestFitBlock& blk) const
  144. {
  145.     if (GetSize() == blk.GetSize())
  146.         return this < &blk;
  147.     else
  148.         return GetSize() < blk.GetSize();
  149. }
  150.  
  151. //----------------------------------------------------------------------------------------
  152. // PrivBestFitBlock::operator ==
  153. //----------------------------------------------------------------------------------------
  154. #pragma segment HeapSeg
  155.  
  156. Boolean PrivBestFitBlock::operator==(const PrivBestFitBlock& blk) const
  157. {
  158.     return GetSize() == blk.GetSize() && this == &blk;
  159. }
  160.  
  161. //----------------------------------------------------------------------------------------
  162. // PrivBestFitBlock::StuffAddressAtEnd
  163. //----------------------------------------------------------------------------------------
  164. #pragma segment HeapSeg
  165.  
  166. void PrivBestFitBlock::StuffAddressAtEnd()
  167. {
  168.     // coalescence possible in constant time.
  169.  
  170.     if (!this->GetBusy())
  171.     {
  172.         void** addr= (void**) ((ODBytePtr) this + this->GetSize() - sizeof(PrivBestFitBlock *));
  173.         *addr = this;
  174.     }
  175. #if MM_DEBUG
  176.     else
  177.         MM_WARN("PrivBestFitBlock::StuffAddressAtEnd: corrupt heap!");
  178. #endif
  179. }
  180.  
  181.  
  182. //========================================================================================
  183. // BestFitHeap
  184. //========================================================================================
  185.  
  186. //----------------------------------------------------------------------------------------
  187. // BestFitHeap::BestFitHeap
  188. //----------------------------------------------------------------------------------------
  189. #pragma segment HeapSeg
  190.  
  191. BestFitHeap::BestFitHeap(unsigned long sizeInitial,
  192.                                  unsigned long sizeIncrement,
  193.                                  unsigned long hugeBlockSize,        // "0" means sizeIncrement/2
  194.                                  MMHeapLocation memSrc) :
  195.     MemoryHeap(false, false, false, memSrc)
  196. {
  197. #if MM_DEBUG
  198.     CompilerCheck();
  199. #endif
  200.  
  201.     fSizeIncrement = sizeIncrement;
  202.     fSizeInitial = sizeInitial;
  203.     
  204.     if( hugeBlockSize!=0 )
  205.         fHugeBlockSize = hugeBlockSize;
  206.     else
  207.         fHugeBlockSize = sizeIncrement>>1;
  208.     
  209.     if( fHugeBlockSize > kMaxHugeBlockSize )
  210.         fHugeBlockSize = kMaxHugeBlockSize;
  211.         
  212.     if( fHugeBlockSize > sizeIncrement ) {
  213.         MM_WARN("hugeSize must be <= sizeIncrement");
  214.         fHugeBlockSize = sizeIncrement;        // Cannot allow range between huge size & sizeIncrement
  215.     }
  216.     
  217.     fSegments = NULL;
  218.     
  219. //    this->GrowHeap(fSizeInitial);    * MEB *
  220. }
  221.  
  222. //----------------------------------------------------------------------------------------
  223. // BestFitHeap::~BestFitHeap
  224. //----------------------------------------------------------------------------------------
  225. #pragma segment HeapSeg
  226.  
  227. BestFitHeap::~BestFitHeap()
  228. {
  229.     this->DeleteSegments();
  230. }
  231.  
  232. //----------------------------------------------------------------------------------------
  233. // BestFitHeap::IBestFitHeap    * MEB *
  234. //----------------------------------------------------------------------------------------
  235. #pragma segment HeapSeg
  236.  
  237. void BestFitHeap::IBestFitHeap()
  238. {
  239.     this->GrowHeap(fSizeInitial);
  240.  
  241. #if MM_DEBUG
  242. #if !defined(qMacApp)
  243.     //SRF - Haven't got CrawlHooks working for MacApp yet!
  244.     ODMemoryHook *hook = new(this->GetLocation()) CBlockStackCrawlHook;
  245.     this->AdoptHook(hook);
  246. #endif
  247.     // Block cushion hooks have to be installed before any blocks are allocated
  248.     // in the heap; so do so now if this is a debug build.
  249.     ODMemoryHook *hook = new(this->GetLocation()) CBlockCushionHook;
  250.     this->AdoptHook(hook);
  251. #endif
  252. }
  253.  
  254. //----------------------------------------------------------------------------------------
  255. // BestFitHeap::ExpandHeap    * MEB *
  256. //----------------------------------------------------------------------------------------
  257. #pragma segment HeapSeg
  258.  
  259. void BestFitHeap::ExpandHeap(unsigned long sizeInitial, unsigned long sizeIncrement)
  260. {
  261.     if (sizeInitial > fSizeInitial)
  262.         fSizeInitial = sizeInitial;
  263.     if (sizeIncrement > fSizeIncrement)
  264.         fSizeIncrement = sizeIncrement;
  265.     
  266.     if (sizeInitial > this->HeapSize())
  267.         this->GrowHeap(sizeInitial);
  268.     else
  269.         this->GrowHeap(sizeIncrement);
  270. }
  271.  
  272. //----------------------------------------------------------------------------------------
  273. // BestFitHeap::BytesFree
  274. //----------------------------------------------------------------------------------------
  275. #pragma segment HeapSeg
  276.  
  277. unsigned long BestFitHeap::BytesFree() const
  278. {
  279.     unsigned long bytesFree, numberOfNodes;
  280.  
  281.     fFreeTree.TreeInfo(bytesFree, numberOfNodes);
  282.     bytesFree -= numberOfNodes * PrivBestFitBlock::kBusyOverhead;
  283.  
  284.     return bytesFree;
  285. }
  286.  
  287. #if MM_DEBUG
  288. //----------------------------------------------------------------------------------------
  289. // BestFitHeap::Check (MM_DEBUG only)
  290. //----------------------------------------------------------------------------------------
  291. #pragma segment HeapSeg
  292.  
  293. void BestFitHeap::Check( HeapWalkProc proc, void *refCon ) const
  294. {
  295.     ODBlockSize blockHeaderSize = this->CallGetHeaderSize();
  296.  
  297.     // ----- validate each segment
  298.     
  299.     PrivBestFitSegment * segment;
  300.     for( segment=fSegments; segment != NULL; segment=segment->fNextSegment )
  301.         if( !segment->CheckSegment(proc,refCon,blockHeaderSize) )
  302.             return;
  303.  
  304.     // ----- check the free tree
  305.     
  306.     fFreeTree.CheckTree();
  307. }
  308. #endif
  309.  
  310. #if MM_DEBUG
  311. //----------------------------------------------------------------------------------------
  312. // BestFitHeap::DoFindBlockContaining (MM_DEBUG only)
  313. //----------------------------------------------------------------------------------------
  314. MMBoolean
  315. BestFitHeap::DoFindBlockContaining( const void *start, const void* end,
  316.                                     const void* &blockStart, const void* &blockEnd ) const
  317. {
  318.     PrivBestFitSegment * segment;
  319.     for( segment=fSegments; segment != NULL; segment=segment->fNextSegment )
  320.         if( segment->FindBlockContaining(start,end, blockStart,blockEnd) )
  321.             return kMMTrue;
  322.     return kMMFalse;
  323. }
  324. #endif
  325.  
  326. //----------------------------------------------------------------------------------------
  327. // BestFitHeap::DoGetBlockHeap
  328. //----------------------------------------------------------------------------------------
  329. #pragma segment HeapSeg
  330.  
  331. MemoryHeap*
  332. BestFitHeap::DoGetBlockHeap( const void *block ) const
  333. {
  334. #if MM_DEBUG
  335.     if(!ValidBlock(block)) {
  336.         MM_WARN("GetBlockHeap(%p): bogus block",block);
  337.         return kMMNULL;
  338.     }
  339. #endif
  340.     
  341.     PrivBestFitBlock * blk
  342.         = (PrivBestFitBlock *) ((ODBytePtr) block - PrivBestFitBlock::kBusyOverhead);
  343.  
  344.     BestFitHeap *heap = blk->GetHeap();
  345. #if MM_DEBUG
  346.     if( !heap->ValidateMagicNumber() )
  347.         return kMMNULL;
  348. #endif
  349.     return heap;
  350. }
  351.  
  352. //----------------------------------------------------------------------------------------
  353. // BestFitHeap::DoAllocate
  354. //----------------------------------------------------------------------------------------
  355. #pragma segment HeapSeg
  356.  
  357. void* BestFitHeap::DoAllocate(ODBlockSize size, ODBlockSize& allocatedSize)
  358. {
  359.     ODBlockSize blkSize = size + PrivBestFitBlock::kBusyOverhead;
  360.  
  361.     if (blkSize < PrivBestFitBlock::kMinBlockSize)
  362.         blkSize = PrivBestFitBlock::kMinBlockSize;
  363.  
  364. #if BLOCKS_ON_4BYTE
  365.     // Make sure blkSize is a multiple of 4 (to keep all blocks on 4byte boundaries)
  366.     // (Added this fix on 7/28/94 on Mike's advice. --jpa)
  367.     blkSize = (blkSize+3) & ~0x03L;
  368. #else
  369.     // Make sure blkSize is even
  370.     if (blkSize & 0x01)
  371.         blkSize++;
  372. #endif
  373.  
  374. #if MM_DEBUG
  375.     MM_ASSERT(blkSize <= BestFitBlock_kMaxBlockSize);
  376. #endif
  377.  
  378.     PrivBestFitBlock * blk;
  379.     
  380.     // A "Huge" block is always allocated its own segment, so the memory can be freed
  381.     // to the platform memory manager as soon as the huge block is deleted:
  382.     
  383.     if( size >= fHugeBlockSize ) {
  384.         blk = this->CreateNewSegment(blkSize + PrivBestFitSegment::kSegmentPrefixSize
  385.                                              + sizeof(PrivBestFitBlock) );
  386.         if( blk )
  387.             MM_ASSERT(blk->GetSize()==blkSize);
  388.             
  389.     } else {
  390.         blk = this->SearchFreeBlocks(blkSize);        // Not huge, so search free blocks
  391.         if (blk == NULL && fSizeIncrement > 0)
  392.         {
  393.             this->GrowHeap(fSizeIncrement);            // Make an attempt to expand the heap
  394.             blk = this->SearchFreeBlocks(blkSize);
  395.         }
  396.     }
  397.  
  398.     allocatedSize = 0;
  399.     void* newPtr = NULL;
  400.  
  401.     if (blk != NULL)
  402.     {
  403.         // We found a block, so mark it busy and remove it from the free list.
  404.  
  405.         blk->SetBusy(true);
  406.         this->RemoveFromFreeBlocks(blk);
  407.         blk->SetHeap(this);
  408.         blk->SetIsObject(false);
  409.  
  410.         if (blk->GetSize() - blkSize >= PrivBestFitBlock::kMinBlockSize)
  411.         {
  412.             // The block is big enough to split, so here we do the split.
  413.  
  414.             PrivBestFitBlock *newBlk
  415.                 = new((void *) ((ODBytePtr) blk + blkSize))
  416.                     PrivBestFitBlock(false, true, blk->GetSize() - blkSize);
  417.             this->AddToFreeBlocks(newBlk);
  418.             blk->SetSize(blkSize);
  419.         }
  420.  
  421.         PrivBestFitBlock * nextBlk
  422.             = (PrivBestFitBlock *) ((ODBytePtr) blk + blk->GetSize());
  423.         nextBlk->SetPrevBusy(true);
  424.  
  425.         newPtr = (void *) ((ODBytePtr) blk + PrivBestFitBlock::kBusyOverhead);
  426.         allocatedSize = blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  427.     }
  428.  
  429.     return newPtr;
  430. }
  431.  
  432. //----------------------------------------------------------------------------------------
  433. // BestFitHeap::DoBlockSize
  434. //----------------------------------------------------------------------------------------
  435. #pragma segment HeapSeg
  436.  
  437. ODBlockSize BestFitHeap::DoBlockSize(const void* block) const
  438. {
  439.     PrivBestFitBlock * blk
  440.         = (PrivBestFitBlock *) ((ODBytePtr) block - PrivBestFitBlock::kBusyOverhead);
  441.  
  442. #if MM_DEBUG
  443.     MM_ASSERT(blk->GetBusy());
  444. #endif
  445.     
  446.     return blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  447. }
  448.  
  449. //----------------------------------------------------------------------------------------
  450. // BestFitHeap::DoFree
  451. //----------------------------------------------------------------------------------------
  452. #pragma segment HeapSeg
  453.  
  454. void BestFitHeap::DoFree(void* ptr)
  455. {
  456.     PrivBestFitBlock *blk
  457.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  458.  
  459. #if MM_DEBUG
  460.     MM_ASSERT(blk->GetBusy());
  461. #endif
  462.     
  463.     blk->SetBusy(false);
  464.     blk->StuffAddressAtEnd();
  465.  
  466.     PrivBestFitBlock *nextBlk
  467.         = (PrivBestFitBlock *) ((ODBytePtr) blk + blk->GetSize());
  468.     nextBlk->SetPrevBusy(false);
  469.  
  470.     if (this->Coalesce(nextBlk))
  471.         this->RemoveFromFreeBlocks(nextBlk);
  472.  
  473.     PrivBestFitBlock * prevBlk = this->Coalesce(blk);
  474.     if (prevBlk)
  475.     {
  476.         this->RemoveFromFreeBlocks(prevBlk);
  477.         //this->AddToFreeBlocks(prevBlk);// Nope, now happens down below unless seg is freed --jpa
  478.         blk = prevBlk;
  479.     }
  480.     
  481.     if( blk->GetIsFirst() ) {
  482.         // If the first block of the segment is free, look just before it for the seg hdr:
  483.         PrivBestFitSegment *segment;
  484.         segment = (PrivBestFitSegment*)( (ODBytePtr)blk - PrivBestFitSegment::kSegmentPrefixSize );
  485. #if MM_DEBUG
  486.         MM_ASSERT(segment->fSegmentSpace==blk);
  487.         MM_ASSERT(blk->GetSize() + sizeof(PrivBestFitBlock) <= segment->fSegmentSize);
  488. #endif
  489.         if( blk->GetSize() + sizeof(PrivBestFitBlock) == segment->fSegmentSize ) {
  490.             this->DeleteSegment(segment);        // Entire seg is free, so delete it
  491.             return;
  492.         }
  493.     }
  494.     
  495.     // If the segment remains, add the free block to the tree:
  496.     this->AddToFreeBlocks(blk);
  497. }
  498.  
  499. //----------------------------------------------------------------------------------------
  500. // BestFitHeap::DoLargestFreeBlock
  501. //----------------------------------------------------------------------------------------
  502. #pragma segment HeapSeg
  503.  
  504. unsigned long BestFitHeap::DoLargestFreeBlock() const
  505. {
  506.     const PrivBestFitBlock *blk = fFreeTree.FindLargestBlock();
  507.     if( blk )
  508.         return blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  509.     else
  510.         return 0;
  511. }
  512.  
  513. #if MM_DEBUG
  514. //----------------------------------------------------------------------------------------
  515. // BestFitHeap::DoIsValidBlock
  516. //----------------------------------------------------------------------------------------
  517. #pragma segment HeapSeg
  518.  
  519. Boolean BestFitHeap::DoIsValidBlock(const void* ptr) const
  520. {
  521.     const PrivBestFitBlock *blk = ValidBlock(ptr);
  522.     if( !blk )
  523.         return kMMFalse;
  524.     else
  525.         // Verify that a huge block must be the first block in its segment:
  526.         return blk->GetIsFirst() || blk->GetSize()<fHugeBlockSize;
  527. }
  528. #endif
  529.  
  530. //----------------------------------------------------------------------------------------
  531. // BestFitHeap::DoReset
  532. //----------------------------------------------------------------------------------------
  533. #pragma segment HeapSeg
  534.  
  535. void BestFitHeap::DoReset()
  536. {
  537.     this->DeleteSegments();
  538.     fSegments = NULL;
  539.     fFreeTree = PrivFreeBlockTree();
  540.  
  541.     this->GrowHeap(fSizeInitial);
  542. }
  543.  
  544. //----------------------------------------------------------------------------------------
  545. // BestFitHeap::HeapSize
  546. //----------------------------------------------------------------------------------------
  547. #pragma segment HeapSeg
  548.  
  549. unsigned long BestFitHeap::HeapSize() const
  550. {
  551.     PrivBestFitSegment * segment = fSegments;
  552.     unsigned long heapSize = 0;
  553.  
  554.     while (segment != NULL)
  555.     {
  556.         heapSize += segment->fSegmentSize;
  557.         segment = segment->fNextSegment;
  558.     }
  559.  
  560.     return heapSize;
  561. }
  562.  
  563.  
  564. //----------------------------------------------------------------------------------------
  565. // BestFitHeap::DoSetBlockIsObject
  566. //----------------------------------------------------------------------------------------
  567. void BestFitHeap::DoSetBlockIsObject( void* ptr, Boolean isObject )
  568. {
  569. #if MM_DEBUG
  570.     MM_ASSERT(this->DoIsValidBlock(ptr));
  571. #endif
  572.     PrivBestFitBlock *blk
  573.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  574.     blk->SetIsObject(isObject);
  575. }
  576.  
  577.  
  578.  
  579. //----------------------------------------------------------------------------------------
  580. // BestFitHeap::DoBlockIsObject
  581. //----------------------------------------------------------------------------------------
  582. Boolean BestFitHeap::DoBlockIsObject( const void* ptr ) const
  583. {
  584. #if MM_DEBUG
  585.     MM_ASSERT(this->DoIsValidBlock(ptr));
  586. #endif
  587.     PrivBestFitBlock *blk
  588.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  589.     return blk->GetIsObject();
  590. }
  591.  
  592.  
  593. #if MM_DEBUG
  594. //----------------------------------------------------------------------------------------
  595. // BestFitHeap::IsMyBlock
  596. //----------------------------------------------------------------------------------------
  597. #pragma segment HeapSeg
  598.  
  599. Boolean BestFitHeap::IsMyBlock(const void* blk) const
  600. {
  601.     Boolean myBlock = false;
  602.  
  603.     PrivBestFitSegment * segment = fSegments;
  604.     while (segment != NULL && myBlock == false)
  605.     {
  606.         myBlock = segment->AddressInSegment(blk);
  607.         segment = segment->fNextSegment;
  608.     }
  609.  
  610.     return myBlock;
  611. }
  612. #endif
  613.  
  614. #if MM_DEBUG
  615. //----------------------------------------------------------------------------------------
  616. // BestFitHeap::Print
  617. //----------------------------------------------------------------------------------------
  618. #pragma segment HeapSeg
  619.  
  620. void BestFitHeap::Print(char* /*msg*/) const
  621. {
  622.     MM_PRINT("********** BestFitHeap **********\n");
  623.     fFreeTree.PrintTree();
  624.     MM_PRINT("\n");
  625. }
  626. #endif
  627.  
  628. //----------------------------------------------------------------------------------------
  629. // BestFitHeap::AddToFreeBlocks
  630. //----------------------------------------------------------------------------------------
  631. #pragma segment HeapSeg
  632.  
  633. void BestFitHeap::AddToFreeBlocks(PrivBestFitBlock* blk)
  634. {
  635.     fFreeTree.AddBlock(blk);
  636. }
  637.  
  638. //----------------------------------------------------------------------------------------
  639. // BestFitHeap::Coalesce: Coalesce blk with the previous block if both are free.
  640. //----------------------------------------------------------------------------------------
  641. #pragma segment HeapSeg
  642.  
  643. PrivBestFitBlock* BestFitHeap::Coalesce(PrivBestFitBlock* blk)
  644. {
  645.     PrivBestFitBlock * prevBlk = NULL;
  646.  
  647.     if (!blk->GetBusy() && !blk->GetPreviousBusy())
  648.     {
  649. #if MM_DEBUG
  650.         if (blk->GetSize() < PrivBestFitBlock::kMinBlockSize)
  651.             MM_WARN("BestFitHeap::Coalesce: corrupt heap!");
  652. #endif
  653.             
  654.         prevBlk = *(PrivBestFitBlock **) ((ODBytePtr) blk - sizeof(ODBlockSize));
  655.         prevBlk->SetSize(prevBlk->GetSize() + blk->GetSize());
  656.         prevBlk->StuffAddressAtEnd();
  657.     }
  658.  
  659.     return prevBlk;
  660. }
  661.  
  662. //----------------------------------------------------------------------------------------
  663. // BestFitHeap::CreateNewSegment
  664. //----------------------------------------------------------------------------------------
  665. #pragma segment HeapSeg
  666.  
  667. PrivBestFitBlock* BestFitHeap::CreateNewSegment(unsigned long size)
  668. {
  669. #ifdef BUILD_WIN16
  670.     MM_ASSERT(size < 64L * 1024L);
  671. #endif
  672.  
  673. #if BLOCKS_ON_4BYTE
  674.     // Make sure size is a multiple of 4 (to keep all blocks on 4byte boundaries)
  675.     // (Added this fix on 7/28/94 on Mike's advice. --jpa)
  676.     size = (size+3) & ~0x03L;
  677.     // For this to work, kSegmentPrefixSize and kSegmentSuffixSize must also be
  678.     // multiples of 4.
  679. #else
  680.     // Make sure segment size is even
  681.     if (size & 0x01)
  682.         size++;
  683. #endif
  684.  
  685.     Boolean disposable = (fSegments!=NULL);        // First segment is NOT disposable
  686.  
  687.     PrivBestFitSegment * segment
  688.         = (PrivBestFitSegment *)this->AllocateRawMemory((ODBlockSize) size);
  689.  
  690.     if (segment == NULL)
  691.         return NULL;
  692.     else {
  693.         // The actual usable space is offset by the size of the fields
  694.         // of a PrivBestFitSegment.
  695.     
  696.         segment->fSegmentSpace 
  697.             = (void *) ((ODBytePtr) segment + PrivBestFitSegment::kSegmentPrefixSize);
  698.         segment->fSegmentSize = size - PrivBestFitSegment::kSegmentPrefixSize;
  699.     
  700.         // Add the segment to the list of segments in this heap.
  701.     
  702.         segment->fNextSegment = fSegments;
  703.         fSegments = segment;
  704.     
  705.         // Suffix the segment with a busy block of zero length so that the last free
  706.         // block is not coalesced with a block past the fEnd of the segment.
  707.     
  708.         void * endOfSegment 
  709.             = (void *) ((ODBytePtr) segment->fSegmentSpace + segment->fSegmentSize);
  710.         PrivBestFitBlock *blk
  711.             = new((void *) ((ODBytePtr) endOfSegment - sizeof(PrivBestFitBlock)))
  712.                 PrivBestFitBlock(true, false, sizeof(PrivBestFitBlock));
  713.         blk->SetHeap(this);
  714.     
  715.         // Create one free block out of this entire segment and Add it to the
  716.         // free block list.
  717.     
  718.         blk = new(segment->fSegmentSpace)PrivBestFitBlock(false, true, segment->fSegmentSize - sizeof(PrivBestFitBlock));
  719.     
  720.         if( disposable )
  721.             // This is the 1st block (positionally) in the heap, so set its bit:  --jpa
  722.             blk->SetIsFirst(true); 
  723.         
  724.         this->AddToFreeBlocks(blk);
  725.         
  726.         return blk;
  727.     }
  728. }
  729.  
  730. //----------------------------------------------------------------------------------------
  731. // BestFitHeap::DeleteSegment
  732. //----------------------------------------------------------------------------------------
  733. #pragma segment HeapSeg
  734.  
  735. void BestFitHeap::DeleteSegment( PrivBestFitSegment *seg )
  736. {
  737.     // The segment MUST be empty, and its single free block
  738.     // must already have been removed from the free block tree.  --jpa
  739.     
  740.     PrivBestFitSegment *segment = fSegments;
  741.     
  742.     if( segment == seg ) {
  743.         fSegments = seg->fNextSegment;
  744.         this->FreeRawMemory(seg);
  745.         return;
  746.         
  747.     } else
  748.         while (segment != NULL)
  749.             if( segment->fNextSegment == seg ) {
  750.                 segment->fNextSegment = seg->fNextSegment;
  751.                 this->FreeRawMemory(seg);
  752.                 return;
  753.             } else
  754.                 segment = segment->fNextSegment;
  755.  
  756.     MM_WARN("Segment not found in list!");
  757. }
  758.  
  759. //----------------------------------------------------------------------------------------
  760. // BestFitHeap::DeleteSegments
  761. //----------------------------------------------------------------------------------------
  762. #pragma segment HeapSeg
  763.  
  764. void BestFitHeap::DeleteSegments()
  765. {
  766.     PrivBestFitSegment * segment = fSegments;
  767.     while (segment != NULL)
  768.     {
  769.         PrivBestFitSegment * nextSegment = segment->fNextSegment;
  770.         this->FreeRawMemory(segment);
  771.         segment = nextSegment;
  772.     }
  773. }
  774.  
  775. //----------------------------------------------------------------------------------------
  776. // BestFitHeap::GrowHeap
  777. //----------------------------------------------------------------------------------------
  778. #pragma segment HeapSeg
  779.  
  780. void BestFitHeap::GrowHeap(unsigned long sizeIncrement)
  781. {
  782. #ifdef BUILD_WIN16
  783.     // To avoid crossing 64K boundries on pointer arithmatic, the size of each segment
  784.     // must be limited to 64K. So a single grow request may result in more than one
  785.     // segment being allocated.
  786.     
  787.     const unsigned long kSegmentSizeLimit = 1024L * 62L;     // Allow for 2K overhead
  788.     
  789.     while (sizeIncrement > 0)
  790.     {
  791.         unsigned long segmentSize = sizeIncrement;
  792.         if (segmentSize > kSegmentSizeLimit)
  793.             segmentSize = kSegmentSizeLimit;
  794.         this->CreateNewSegment(segmentSize);
  795.         sizeIncrement -= segmentSize;
  796.     }
  797. #else
  798.     this->CreateNewSegment(sizeIncrement);
  799. #endif
  800. }
  801.  
  802. //----------------------------------------------------------------------------------------
  803. // BestFitHeap::RemoveFromFreeBlocks
  804. //----------------------------------------------------------------------------------------
  805. #pragma segment HeapSeg
  806.  
  807. void BestFitHeap::RemoveFromFreeBlocks(PrivBestFitBlock* blk)
  808. {
  809.     fFreeTree.RemoveBlock(blk);
  810. }
  811.  
  812. //----------------------------------------------------------------------------------------
  813. // BestFitHeap::SearchFreeBlocks
  814. //----------------------------------------------------------------------------------------
  815. #pragma segment HeapSeg
  816.  
  817. PrivBestFitBlock* BestFitHeap::SearchFreeBlocks(ODBlockSize size)
  818. {
  819.     //all blocks are of even length, so round up to fNext even number
  820.  
  821.     if (size & 1)
  822.         size++;
  823.  
  824.     return fFreeTree.SearchForBlock(size, NULL, NULL);
  825. }
  826.  
  827. #if MM_DEBUG
  828. //----------------------------------------------------------------------------------------
  829. // BestFitHeap::CompilerCheck
  830. //----------------------------------------------------------------------------------------
  831. #pragma segment HeapSeg
  832.  
  833. void BestFitHeap::CompilerCheck()
  834. {
  835.     MemoryHeap::CompilerCheck();
  836.     
  837.     char buffer[sizeof(PrivBestFitBlock) + sizeof(void *)];
  838.     PrivBestFitBlock &block = *((PrivBestFitBlock *) buffer);
  839.         
  840.     // Check to make sure the bit field setters and getters work.
  841.     
  842.     block.SetBlockType(3);
  843.     block.SetBusy(true);
  844.     block.SetPrevBusy(false);
  845. #ifndef BUILD_WIN16
  846.     block.SetSize(100201);
  847. #endif
  848.     block.SetMagicNumber(3);
  849.  
  850.     MM_ASSERT(block.GetBlockType() == 3);
  851.     MM_ASSERT(block.GetBusy() == true);
  852.     MM_ASSERT(block.GetPreviousBusy() == false);
  853. #ifndef BUILD_WIN16
  854.     MM_ASSERT(block.GetSize() == 100201);
  855. #endif
  856.     MM_ASSERT(block.GetMagicNumber() == 3);
  857.     
  858.     block.SetBlockType(2);
  859.     block.SetBusy(false);
  860.     block.SetPrevBusy(true);
  861.     block.SetSize(150);
  862.     block.SetMagicNumber(2);
  863.  
  864.     MM_ASSERT(block.GetBlockType() == 2);
  865.     MM_ASSERT(block.GetBusy() == false);
  866.     MM_ASSERT(block.GetPreviousBusy() == true);
  867.     MM_ASSERT(block.GetSize() == 150);
  868.     MM_ASSERT(block.GetMagicNumber() == 2);
  869. }
  870. #endif
  871.  
  872.  
  873. //========================================================================================
  874. // CLASS PrivFreeBlockTree
  875. //========================================================================================
  876.  
  877. //----------------------------------------------------------------------------------------
  878. // PrivBestFitSegment::CheckSegment
  879. //----------------------------------------------------------------------------------------
  880.  
  881. Boolean PrivBestFitSegment::CheckSegment( HeapWalkProc proc, void *refCon, ODBlockSize hdrSize )
  882. {
  883.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  884.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  885.     unsigned long blksScanned = 0;
  886.  
  887.     // ----- spin through all the blocks in segment do some consistency checks
  888.     
  889.     while (blk < segmentEnd)
  890.     {
  891.         PrivBestFitBlock *nextBlk;
  892.         MM_ASSERT(blk->GetMagicNumber() == PrivBestFitBlock::kMagicNumber);
  893.         MM_ASSERT(blk->GetBlockType() == PrivBestFitBlock::kBlockTypeId);
  894.         nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  895.         if (nextBlk < segmentEnd)
  896.             MM_ASSERT(nextBlk->GetPreviousBusy() == blk->GetBusy());
  897.         
  898.         if( proc )            // Call user proc if they supplied one
  899.             if( blk->GetBusy() && nextBlk<segmentEnd ) {
  900.                 ODBytePtr userBlk = (ODBytePtr)blk + PrivBestFitBlock::kBusyOverhead + hdrSize;
  901.                 if( (*proc)((void*)userBlk, blk->GetSize()-hdrSize, blk->GetIsObject(), refCon) == false )
  902.                     return false;        // proc can return false to abort
  903.             }
  904.         
  905.         blksScanned++;
  906.         blk = nextBlk;
  907.     }
  908.  
  909.     // ----- if sizes are valid we should be exactly at the end of the segment
  910.     
  911.     MM_ASSERT(blk == segmentEnd);
  912.     return true;
  913. }
  914.  
  915. #if MM_DEBUG
  916. //----------------------------------------------------------------------------------------
  917. // PrivBestFitSegment::FindBlockContaining
  918. //----------------------------------------------------------------------------------------
  919.  
  920. MMBoolean
  921. PrivBestFitSegment::FindBlockContaining( const void *start, const void* end,
  922.                                          const void* &blockStart, const void* &blockEnd ) const
  923. {
  924.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  925.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  926.     
  927.     if( end<=blk || start>=segmentEnd )
  928.         return kMMFalse;
  929.     else {
  930.         // Memory range intersects range of this segment:
  931.         while (blk < segmentEnd)
  932.         {
  933.             blockStart = blockEnd = NULL;
  934.             PrivBestFitBlock *nextBlk;
  935.             nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  936.             if( blk->GetBusy() && nextBlk<segmentEnd ) {
  937.                 if( start <= nextBlk ) {
  938.                     // The memory range starts before the next block, so return:
  939.                     blockStart = (char*)blk + PrivBestFitBlock::kBusyOverhead;
  940.                     blockEnd   = nextBlk;
  941.                     break;
  942.                 }
  943.             }
  944.             blk = nextBlk;
  945.         }
  946.         return kMMTrue;
  947.     }
  948. }
  949.  
  950. #endif
  951.  
  952.  
  953. //========================================================================================
  954. // CLASS PrivFreeBlockTree
  955. //========================================================================================
  956.  
  957. //----------------------------------------------------------------------------------------
  958. // PrivFreeBlockTree::PrivFreeBlockTree
  959. //----------------------------------------------------------------------------------------
  960. #pragma segment HeapSeg
  961.  
  962. PrivFreeBlockTree::PrivFreeBlockTree() :
  963.     fRoot(true, true, 0)
  964. {
  965.     fRoot.SetRight(NULL);
  966.     fRoot.SetLeft(NULL);
  967. }
  968.  
  969. //----------------------------------------------------------------------------------------
  970. // PrivFreeBlockTree::PrivFreeBlockTree
  971. //----------------------------------------------------------------------------------------
  972. #pragma segment HeapSeg
  973.  
  974. PrivFreeBlockTree::PrivFreeBlockTree(const PrivFreeBlockTree& blk) :
  975.     fRoot(blk.fRoot)
  976. {
  977. }
  978.  
  979. //----------------------------------------------------------------------------------------
  980. // PrivFreeBlockTree::operator=
  981. //----------------------------------------------------------------------------------------
  982. #pragma segment HeapSeg
  983.  
  984. PrivFreeBlockTree& PrivFreeBlockTree::operator=(const PrivFreeBlockTree& blk)
  985. {
  986.     fRoot = blk.fRoot;
  987.     return (*this);
  988. }
  989.  
  990. //----------------------------------------------------------------------------------------
  991. // PrivFreeBlockTree::AddBlock
  992. //----------------------------------------------------------------------------------------
  993. #pragma segment HeapSeg
  994.  
  995. void PrivFreeBlockTree::AddBlock(PrivBestFitBlock* blk)
  996. {    
  997. #if MM_DEBUG
  998.     if( gValidate>0 )
  999.         this->CheckTree();
  1000.  
  1001. #ifdef OD_INTENSE_DEBUG
  1002.     MM_PRINT("PrivFreeBlockTree::AddBlock Entry-------------------------------------\n");
  1003.     this->PrintTree();
  1004. #endif
  1005. #endif
  1006.  
  1007.     PrivBestFitBlock * parent;
  1008.  
  1009.     this->SearchForBlock(blk->GetSize(), blk, &parent);
  1010.  
  1011.     blk->SetRight(NULL);
  1012.     blk->SetLeft(NULL);
  1013.     blk->SetParent(parent);
  1014.  
  1015.     if (*blk > *parent)
  1016.         parent->SetRight(blk);
  1017.     else
  1018.         parent->SetLeft(blk);
  1019.  
  1020. #if MM_DEBUG
  1021.     if( gValidate>0 )
  1022.         this->CheckTree();
  1023.  
  1024. #ifdef OD_INTENSE_DEBUG
  1025.     MM_PRINT("PrivFreeBlockTree::AddBlock Exit\n");
  1026.     this->PrintTree();
  1027.     MM_PRINT("\n");
  1028. #endif
  1029. #endif
  1030. }
  1031.  
  1032. #if MM_DEBUG
  1033. //----------------------------------------------------------------------------------------
  1034. // PrivFreeBlockTree::CheckTree
  1035. //----------------------------------------------------------------------------------------
  1036. #pragma segment HeapSeg
  1037.  
  1038. void PrivFreeBlockTree::CheckTree() const
  1039. {
  1040.     this->CheckTreeHelper(&((PrivFreeBlockTree *)this)->fRoot);
  1041. }
  1042. #endif
  1043.  
  1044. #if MM_DEBUG
  1045. //----------------------------------------------------------------------------------------
  1046. // PrivFreeBlockTree::PrintTree
  1047. //----------------------------------------------------------------------------------------
  1048. #pragma segment HeapSeg
  1049.  
  1050. void PrivFreeBlockTree::PrintTree() const
  1051. {
  1052.     this->PrintTreeHelper(&((PrivFreeBlockTree *)this)->fRoot);
  1053. }
  1054. #endif
  1055.  
  1056. //----------------------------------------------------------------------------------------
  1057. // PrivFreeBlockTree::RemoveBlock
  1058. //----------------------------------------------------------------------------------------
  1059. #pragma segment HeapSeg
  1060.  
  1061. void PrivFreeBlockTree::RemoveBlock(PrivBestFitBlock* blk)
  1062. {
  1063. #if MM_DEBUG
  1064.     if( gValidate > 0 )
  1065.         this->CheckTree();
  1066.  
  1067. #ifdef OD_INTENSE_DEBUG
  1068.     MM_PRINT("PrivFreeBlockTree::RemoveBlock Entry----------------------------------\n");
  1069.     this->PrintTree();
  1070. #endif
  1071. #endif
  1072.  
  1073.     PrivBestFitBlock * spliceOutBlk;
  1074.  
  1075.     // Decide which block to splice out of the tree. Either the block being
  1076.     // removed, or its successor block in the tree.
  1077.  
  1078.     if (blk->GetLeft() == NULL || blk->GetRight() == NULL)
  1079.         spliceOutBlk = blk;
  1080.     else
  1081.         spliceOutBlk = this->GetSuccessorBlk(blk);
  1082.  
  1083.     // Splice the node out of the tree
  1084.  
  1085.     PrivBestFitBlock * tmp;
  1086.     PrivBestFitBlock * parent = spliceOutBlk->GetParent();
  1087.     if (spliceOutBlk->GetLeft())
  1088.         tmp = spliceOutBlk->GetLeft();
  1089.     else
  1090.         tmp = spliceOutBlk->GetRight();
  1091.     if (tmp)
  1092.         tmp->SetParent(parent);
  1093.     if (spliceOutBlk == parent->GetLeft())
  1094.         parent->SetLeft(tmp);
  1095.     else
  1096.         parent->SetRight(tmp);
  1097.  
  1098.     // If we spliced out the successor to blk above then we need to patch the successor
  1099.     // back in, in Place of blk.
  1100.  
  1101.     if (spliceOutBlk != blk)
  1102.     {
  1103.         PrivBestFitBlock * parent = blk->GetParent();
  1104.  
  1105.         // Fix up the parent's child pointer.
  1106.  
  1107.         if (parent->GetLeft() == blk)
  1108.             parent->SetLeft(spliceOutBlk);
  1109.         else
  1110.             parent->SetRight(spliceOutBlk);
  1111.  
  1112.         // Fix up the splice in block's pointers.
  1113.  
  1114.         spliceOutBlk->SetParent(parent);
  1115.         spliceOutBlk->SetLeft(blk->GetLeft());
  1116.         spliceOutBlk->SetRight(blk->GetRight());
  1117.  
  1118.         // Fix up the children of the splice in block's parent pointers.
  1119.  
  1120.         if (spliceOutBlk->GetLeft())
  1121.             (spliceOutBlk->GetLeft())->SetParent(spliceOutBlk);
  1122.         if (spliceOutBlk->GetRight())
  1123.             (spliceOutBlk->GetRight())->SetParent(spliceOutBlk);
  1124.     }
  1125.  
  1126. #if MM_DEBUG
  1127.     if( gValidate>0 )
  1128.         this->CheckTree();
  1129.  
  1130. #ifdef OD_INTENSE_DEBUG
  1131.     MM_PRINT("PrivFreeBlockTree::RemoveBlock Exit\n");
  1132.     this->PrintTree();
  1133.     MM_PRINT("\n");
  1134. #endif
  1135. #endif
  1136. }
  1137.  
  1138. //----------------------------------------------------------------------------------------
  1139. // PrivFreeBlockTree::SearchForBlock
  1140. //----------------------------------------------------------------------------------------
  1141. #pragma segment HeapSeg
  1142.  
  1143. PrivBestFitBlock* PrivFreeBlockTree::SearchForBlock(ODBlockSize size,
  1144.                                             void* blk,
  1145.                                             PrivBestFitBlock** insertLeaf)
  1146. {
  1147. #if MM_DEBUG
  1148.     if( gValidate>0 )
  1149.         this->CheckTree();
  1150.  
  1151. #ifdef OD_INTENSE_DEBUG
  1152.     char str[80];
  1153.     sprintf(str, "PrivFreeBlockTree::SearchForBlock(%d)---------------------------------\n", size);
  1154.     MM_PRINT(str);
  1155.     this->PrintTree();
  1156. #endif
  1157. #endif
  1158.  
  1159.     long minDiff = LONG_MAX;
  1160.     PrivBestFitBlock * minDiffBlock = NULL;
  1161.     PrivBestFitBlock * currentBlock = &fRoot;
  1162.     do
  1163.     {
  1164.         long diff = currentBlock->GetSize() - size;
  1165.         if (diff >= 0 && diff < minDiff)
  1166.         {
  1167.             minDiffBlock = currentBlock;
  1168.             minDiff = diff;
  1169.         }
  1170.  
  1171.         if (insertLeaf)
  1172.             *insertLeaf = currentBlock;
  1173.  
  1174.         // Determine which branch of the tree to continue down. Since duplicate keys are
  1175.         // difficult to deal with in binary trees, we use the address of blocks to break
  1176.         // ties, in the case of two blocks whose size are equal.
  1177.  
  1178.         if (size < currentBlock->GetSize())
  1179.             currentBlock = currentBlock->GetLeft();
  1180.         else if (size > currentBlock->GetSize())
  1181.             currentBlock = currentBlock->GetRight();
  1182.         else if (blk)
  1183.         {
  1184.             if (blk <= currentBlock)
  1185.                 currentBlock = currentBlock->GetLeft();
  1186.             else
  1187.                 currentBlock = currentBlock->GetRight();
  1188.         }
  1189.         else
  1190.             currentBlock = currentBlock->GetLeft();
  1191.  
  1192.     } while (currentBlock != NULL);
  1193.  
  1194.     return minDiffBlock;
  1195. }
  1196.  
  1197. //----------------------------------------------------------------------------------------
  1198. // PrivFreeBlockTree::FindLargestBlock
  1199. //----------------------------------------------------------------------------------------
  1200. #pragma segment HeapSeg
  1201.  
  1202. const PrivBestFitBlock* PrivFreeBlockTree::FindLargestBlock( ) const
  1203. {
  1204.     // The block to the right in the tree is always larger...
  1205.     
  1206.     const PrivBestFitBlock * currentBlock = &fRoot;
  1207.     const PrivBestFitBlock * nextBlock;
  1208.     while( (nextBlock = currentBlock->GetRight()) != kMMNULL )
  1209.         currentBlock = nextBlock;
  1210.     return currentBlock;
  1211. }
  1212.  
  1213. //----------------------------------------------------------------------------------------
  1214. // PrivFreeBlockTree::TreeInfo
  1215. //----------------------------------------------------------------------------------------
  1216. #pragma segment HeapSeg
  1217.  
  1218. void PrivFreeBlockTree::TreeInfo(unsigned long& bytesFree,
  1219.                              unsigned long& numberOfNodes) const
  1220. {
  1221.     bytesFree = numberOfNodes = 0;
  1222.     this->TreeInfoHelper(&((PrivFreeBlockTree *)this)->fRoot, bytesFree, numberOfNodes);
  1223.  
  1224.     // Subtract one from the number of nodes to account for the header node which
  1225.     // is always empty.
  1226.  
  1227.     numberOfNodes--;
  1228. }
  1229.  
  1230. #if MM_DEBUG
  1231. //----------------------------------------------------------------------------------------
  1232. // PrivFreeBlockTree::CheckTreeHelper
  1233. //----------------------------------------------------------------------------------------
  1234. #pragma segment HeapSeg
  1235.  
  1236. void PrivFreeBlockTree::CheckTreeHelper(PrivBestFitBlock* blk) const
  1237. {
  1238.     if (blk == NULL)
  1239.         return;
  1240.  
  1241.     this->CheckTreeHelper(blk->GetLeft());
  1242.  
  1243.     PrivBestFitBlock * parent = blk->GetParent();
  1244.     if (parent != NULL)
  1245.     {
  1246.         if (parent->GetRight() == blk)
  1247.         {
  1248.             if (*blk < *parent)
  1249.             {
  1250.                 this->PrintTree();
  1251.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1252.                                              "Corrupt free list tree: "
  1253.                                              "right child less than parent.");
  1254.             }
  1255.         }
  1256.         else if (parent->GetLeft() == blk)
  1257.         {
  1258.             if (*blk > *parent)
  1259.             {
  1260.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1261.                                              "Corrupt free list tree: "
  1262.                                              "left child greater than parent.");
  1263.             }
  1264.         }
  1265.         else
  1266.         {
  1267.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1268.                                              "Corrupt free list tree: "
  1269.                                              "I am not my parent's child.");
  1270.         }
  1271.     }
  1272.  
  1273.     // AMB_TODO: Recursing down the right side of the tree trashes the tree. This is
  1274.     //             very strange, and as of yet I don't understand what the problem is. I
  1275.     //             had suspected stack over-run.
  1276.     //this->CheckTreeHelper(blk->GetRight());
  1277. }
  1278. #endif
  1279.  
  1280. //----------------------------------------------------------------------------------------
  1281. // PrivFreeBlockTree::GetSuccessorBlk
  1282. //----------------------------------------------------------------------------------------
  1283. #pragma segment HeapSeg
  1284.  
  1285. PrivBestFitBlock* PrivFreeBlockTree::GetSuccessorBlk(PrivBestFitBlock* blk)
  1286. {
  1287.     if (blk->GetRight())
  1288.     {
  1289.         PrivBestFitBlock * current = blk->GetRight();
  1290.         while (current->GetLeft())
  1291.             current = current->GetLeft();
  1292.         return current;
  1293.     }
  1294.     else
  1295.     {
  1296.         PrivBestFitBlock * parent = blk->GetParent();
  1297.         PrivBestFitBlock * current = NULL;
  1298.         while (parent != NULL && current == parent->GetRight())
  1299.         {
  1300.             current = parent;
  1301.             parent = parent->GetParent();
  1302.         }
  1303.         return parent;
  1304.     }
  1305. }
  1306.  
  1307. #if MM_DEBUG
  1308. //----------------------------------------------------------------------------------------
  1309. // PrivFreeBlockTree::PrintTreeHelper
  1310. //----------------------------------------------------------------------------------------
  1311. #pragma segment HeapSeg
  1312.  
  1313. void PrivFreeBlockTree::PrintTreeHelper(PrivBestFitBlock* blk,
  1314.                                         int level) const
  1315. {
  1316.     for (int i = 0; i < level; i++)
  1317.         MM_PRINT("\t");
  1318.  
  1319.     if (blk == NULL)
  1320.     {
  1321.         MM_PRINT("NULL\n");
  1322.         return;
  1323.     }
  1324.  
  1325.     char str[80];
  1326.     //sprintf(str, "Block=%lx fSize=%ld\n", blk, blk->GetSize());
  1327.     MM_PRINT(str);
  1328.  
  1329.     this->PrintTreeHelper(blk->GetLeft(), level + 1);
  1330.     this->PrintTreeHelper(blk->GetRight(), level + 1);
  1331. }
  1332. #endif
  1333.  
  1334. //----------------------------------------------------------------------------------------
  1335. // PrivFreeBlockTree::TreeInfoHelper
  1336. //----------------------------------------------------------------------------------------
  1337. #pragma segment HeapSeg
  1338.  
  1339. void PrivFreeBlockTree::TreeInfoHelper(PrivBestFitBlock* blk,
  1340.                                        unsigned long& bytesFree,
  1341.                                        unsigned long& numberOfNodes) const
  1342. {
  1343.     if (blk == NULL)
  1344.         return;
  1345.  
  1346.     this->TreeInfoHelper(blk->GetLeft(), bytesFree, numberOfNodes);
  1347.  
  1348.     numberOfNodes++;
  1349.     bytesFree += blk->GetSize();
  1350.  
  1351.     this->TreeInfoHelper(blk->GetRight(), bytesFree, numberOfNodes);
  1352. }
  1353.